'''
https://leetcode.cn/problems/merge-k-sorted-lists/
'''
from typing import List, Optional

from c03_list.utils import ListNode
import heapq


class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 使用优先级队列
        # 这个mask是唯一标识，目的是为了，heapq不提供自定义比较器，我们传入元组，来让他实现默认比较，
        # 但是当val相等的时候他就开始比较tuple下一个元素了。
        # 所以我们使用mask做标识，当相等的时候无所谓谁小谁大，或者说，我门这个使用时谁先进谁小
        mask = 0
        if not lists: return None
        heap = []
        for list in lists:
            if list:
                heapq.heappush(heap, (list.val, mask, list))
            mask += 1
        head = ListNode(-1)
        cur = head
        while heap:
            _, _, small = heapq.heappop(heap)
            small_next = small.next
            if small_next:
                heapq.heappush(heap, (small_next.val,mask, small_next))
                mask += 1
            cur.next = small
            cur = cur.next
        return head.next

    def mergeKLists2(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 使用辅助数组，将所有元素放入，然后排序，然后串起来。最后返回
        pass

    def mergeKLists3(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 使用归并思想
        def process(l, r) -> ListNode:
            if l == r: return lists[l]
            m = (l + r) // 2
            l1 = process(l, m)
            l2 = process(m + 1, r)
            return merge(l1, l2)
        def merge(l1, l2) -> ListNode:
            watch_dog = ListNode()
            cur = watch_dog
            while l1 and l2:
                if l1.val < l2.val:
                    cur.next = l1
                    l1 = l1.next
                else:
                    cur.next = l2
                    l2 = l2.next
                cur = cur.next
            cur.next = l1 if l1 else l2
            return watch_dog.next
        return process(0, len(lists) - 1) if lists else None